﻿public class Solution {
    public int LongestPalindromeSubseq(string s)
    {
        int[,] dp = new int[s.Length, s.Length];

        for (int i = s.Length - 1; i >= 0; i--)
        {
            for (int j = i; j < s.Length; j++)
            {
                if (i == j) dp[i, j] = 1;
                else if (s[i] == s[j])
                {
                    if (i + 1 == j) dp[i, j] = 2;
                    else dp[i, j] = dp[i + 1, j - 1] + 2;
                }
                else
                {
                    dp[i, j] = Math.Max(dp[i + 1, j], dp[i, j - 1]);
                }
            }
        }

        return dp[0, s.Length - 1];
    }

    public static void Main(string[] args)
    {
        string s = "bbbab";

        Solution solution = new Solution();
        int res = solution.LongestPalindromeSubseq(s);
        Console.WriteLine(res);
    }
}